import collections
import math
class Solution(object):
    def waysToBuildRooms(self, prevRoom):
        base = 10 ** 9 + 7
        d = collections.defaultdict(set)
        for index, num in enumerate(prevRoom):
            d[num].add(index)
        def dfs(node):
            now_node = 1
            left_node = 0
            now_count = 1
            for v in d[node]:
                temp_node, temp_count = dfs(v)
                now_node += temp_node
                now_count = (now_count * temp_count * math.comb(left_node + temp_node, left_node)) % base
                left_node += temp_node
            return now_node, now_count
        return dfs(-1)[1]




data = Solution()
prevRoom = [-1,0,0,1,2]
print(data.waysToBuildRooms(prevRoom))
prevRoom = [-1,0,1]
print(data.waysToBuildRooms(prevRoom))